package query

// 从升序数组找到匹配值
func binaryQuery(nums []int, target int) int {
	low, high := 0, len(nums)-1

	for low <= high {
		mid := getIntMid(low, high)

		if nums[mid] == target {
			return mid
		}

		if nums[mid] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}

// 变体一：查找第一个值等于给定值的元素
func queryFirstEqual(nums []int, target int) int {
	low, high := 0, len(nums)-1

	for low <= high {
		mid := getIntMid(low, high)

		if nums[mid] == target && (mid == 0 || nums[mid-1] != target) {
			return mid
		} else if nums[mid] == target && nums[mid-1] == target {
			high = mid - 1
		}

		if nums[mid] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}

	}
	return -1
}

// 变体二：查找最后一个值等于给定值的元素
func queryLastEqual(nums []int, target int) int {
	low, high := 0, len(nums)-1

	for low <= high {
		mid := getIntMid(low, high)

		if nums[mid] == target && (mid == len(nums)-1 || nums[mid+1] != target) {
			return mid
		} else if nums[mid] == target && nums[mid+1] == target {
			low = mid + 1
		}

		if nums[mid] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}

	}
	return -1
}

// 变体三：查找第一个大于等于给定值的元素
func queryFirstGreaterThanOrEqual(nums []int, target int) int {
	low, high := 0, len(nums)-1

	for low <= high {
		mid := getIntMid(low, high)

		if nums[mid] < target {
			low = mid + 1
		} else {
			if mid == 0 || nums[mid-1] < target {
				return mid
			} else {
				high = mid - 1
			}
		}

	}
	return -1
}

// 变体四：查找最后一个小于等于给定值的元素
func queryLastLessThanOrEqual(nums []int, target int) int {
	low, high := 0, len(nums)-1

	for low <= high {
		mid := getIntMid(low, high)

		if nums[mid] > target {
			high = mid - 1
		} else {
			if mid == len(nums)-1 || nums[mid+1] > target {
				return mid
			} else {
				low = mid + 1
			}
		}
	}
	return -1
}
